package 排序.插入排序;

import 排序.IArraySort;

import java.util.Arrays;

/**
 * @author zc
 * @version 1.0
 * @date 2021/9/30 11:49
 */
public class InsertSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) {

        //对arr进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray,sourceArray.length);

        //从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 0; i < arr.length; i++) {
            //记录要插入的数据
            int tmp = arr[i];

            //从已经排序的序列最右边的开始比较，找到比其小的数
            int j = i;
            while(j>0&&tmp<arr[j-1]){
                arr[j]=arr[j-1];
                j--;
            }
            //存在比其小的数字 插入
            if(j!=i){
                arr[j]=tmp;
            }
        }

        return arr;
    }


    public static void main(String[] args) {
        InsertSort insertSort = new InsertSort();
        int[] a = {1,5,4,3,2,9,7,8};
        int[] sort = insertSort.sort(a);
        for (int i : sort) {
            System.out.print(i+" ");
        }
    }
}
